package com.liufei1988.sort;

public class QuikSort {

    /**
     * 快速排序
     * @param a 数组
     * @param n 数组大小
     */
   public static void quickSort(int[] a,int n){
         quickSortInternally(a,0,n-1);
   }

   public static void quickSortInternally(int[] a,int left,int right){
       if (left>=right) return;
       int pivot=partition(a,left,right);
       quickSortInternally(a,left,pivot-1);
       quickSortInternally(a,pivot+1,right);

   }
   private static int partition(int[] a,int left,int right){
       int pivot=a[right];
       int i=left;
       for (int j=left;j<right;++j){
           if (a[j]<pivot){
               if (i==j){
                   ++i;
               }else {
                   int tmp=a[i];
                   a[i++]=a[j];
                   a[j]=tmp;
               }
           }
       }
       int tmp=a[i];
       a[i]=a[right];
       a[right]=tmp;
       return i;

   }


    public static void main(String[] args) {
        int[] a={10,20,9,30,8,22,11};
        quickSort(a,a.length);
        for (int s:a){
            System.out.print(s+"   ");
        }
    }
}
